import java.util.Arrays;

public class Search {
	public static void main(String[] args) {
		int[] arr = { 1,4,7,8,9,12,16,17,19,23};
		System.out.println(Arrays.toString(Arrays.copyOf(arr, 5)));
		System.out.println(orderSearch(arr, 7));
		System.out.println(binarySearch(arr, 1));
		System.out.println(binarySearch1(arr, 0, arr.length-1, 1));
	}

	static int orderSearch(int[] arr, int num) {
		for (int j = 0; j < arr.length; j++) {
			if (num == arr[j]) {
				return j;
			}
		}
		return -1;
	}

	/**
	 * m >> n = m/2^n m << n = m*2^n
	 * 
	 * @param arr
	 * @param num
	 * @return
	 */
	static int binarySearch(int[] arr, int num) {
		// 中间索引
		int low = 0;
		int height = arr.length - 1;
		while (low <= height) {
			int middle = low + (height - low) >>> 1;//(low + height) >> 1;
			if (arr[middle] == num) {
				return middle;
			}
			if (num > arr[middle]) {
				low = middle + 1;
			}
			
			if (num < arr[middle]) {
				height = middle - 1;
			}
		}
		return -1;
	}
	
	
	static int binarySearch1(int[] arr,int low,int height, int num) {
		if (low > height) {
			return -(low+1);
		}
		
		int middle = low + (height - low) >>> 1;
		
		if (num == arr[middle]) {
			return middle;
		}
		
		if (num < arr[middle]) {
			return binarySearch1(arr,low,middle-1,num);
		}
		
		return binarySearch1(arr, middle + 1, height, num);
	}

}
